package 数据结构专栏.C_排序算法;

import java.util.Arrays;

/**
 * @Title https://blog.csdn.net/w627947015/article/details/64125079
 * @Author zhengqiang.tan
 * @Date 2021/4/17 10:06 PM
 *
 * 快速排序基于分治思想，它的时间平均复杂度很容易计算得到为O(NlogN)。
 * https://zhuanlan.zhihu.com/p/266482501
 */
public class 快速排序 {
    public static int[] arr = new int[]{0, 3, 2, 1, 9, 8, 5, 6, 7, 4};

    public static void main(String[] args) {
        System.out.println(Arrays.toString(arr));

        int[] sort = new 快速排序().quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(sort));
        //[0, 3, 2, 1, 9, 8, 5, 6, 7, 4]
        //[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]


//        int[] mysort = mySort(arr, 0, arr.length - 1);
//        System.out.println(Arrays.toString(mysort));

    }


    /**
     * 递归
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }

    private int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }


    // 示例2
    public static int[] mySort(int[] arr, int low, int high) {
        int start = low;
        int end = high;
        //定义基准值
        int key = arr[low];
        //整体判断条件，从后往前的索引大于从前往后的索引的情况下
        while (end > start) {
            //如果最后一个元素大于基准值，就比较倒数第二个，直到有比基准值小的元素出现，然后交换位置
            while (end > start && arr[end] >= key) {
                end--;
            }
            //元素交换位置
            if (arr[end] <= key) {
                int tmp = arr[end];
                arr[end] = arr[start];
                arr[start] = tmp;
            }
            //如果第一个元素小于基准值，就比较第二个，直到有比基准值大的元素出现，然后交换位置
            while ((end > start && arr[start] <= key)) {
                start++;
            }
            //元素交换位置
            if (arr[start] >= key) {
                int tmp = arr[start];
                arr[start] = arr[end];
                arr[end] = tmp;
            }
        }
        //递归调用函数，对基准值左边的元素进行排序
        if (start > low) {
            mySort(arr, low, start - 1);
        }
        //递归调用函数，对基准值右边的元素进行排序
        if (end < high) {
            mySort(arr, end + 1, high);
        }
        return arr;
    }

}
